문서의 임의 삭제는 제재 대상으로, 문서를 삭제하려면 삭제 토론을 진행해야 합니다. 문서 보기문서 삭제토론 정렬 알고리즘 (문단 편집) ==== 삽입 정렬(Insertion sort) ==== [youtube(ROalU379l3U)] [[파일:external/upload.wikimedia.org/Insertion-sort-example-300px.gif]] 삽입 정렬을 알기 쉽게 만든 그림. 선택 정렬과 함께 인간에게 뭔가를 정렬하라고 하면 무의식적으로 사용하는 대표적인 알고리즘이다.[* 예를 들어 [[트럼프(카드)|카드 게임]]을 할 때나 번호대로 도서를 정리할 때. 필요한 임시 저장공간이 적고 컴퓨터와 달리 자료들을 밀어낼 때 소요시간이 없기 때문] k번째 원소를 1부터 k-1까지와 비교해 적절한 위치에 끼워넣고 그 뒤의 자료를 한 칸씩 뒤로 밀어내는 방식으로, 평균적으론 [math(\mathcal{O}(n^2))]중 빠른 편이나[* 최악의 경우가 [math(\displaystyle \frac{n(n-1)}{2})]에 비례한다.] 자료구조에 따라선 뒤로 밀어내는데 걸리는 시간이 크며, 앞의 예시처럼 작은 게 뒤쪽에 몰려있으면(내림차순의 경우 큰 게 뒤쪽에 몰려있으면) 그야말로 헬게이트다. 다만 이미 정렬되어 있는 자료구조에 자료를 하나씩 삽입/제거하는 경우에는 현실적으로 최고의 정렬 알고리즘이 되는데, 탐색을 제외한 오버헤드가 매우 적기 때문이다. ~~괜히 '삽입'이란 이름이 붙은 것이 아니다.~~ 그밖에도 배열이 작을 경우에 역시 상당히 효율적이다. 일반적으로 빠르다고 알려진 알고리즘들도 배열이 작을 경우에는 대부분 삽입 정렬에 밀린다. 따라서 고성능 알고리즘들 중에서는 배열의 사이즈가 클때는 [math(\mathcal{O}(n\log n))] 알고리즘을 쓰다가 정렬해야 할 부분이 작을때 는 삽입 정렬로 전환하는 것들도 있다. 또 굳이 장점을 뽑자면 구현이 매우 쉽다는 것. 그 예로 C/C++에서 기본적인 삽입 정렬을 구현하는데는 서너줄의 코드면 충분하다. {{{#!folding [짧은 C++ 삽입 정렬 코드] {{{#!syntax cpp #include template void insertionSort(std::vector& vec, const int& left, const int& right){ for (int i = left; i < right; ++i){ for (int j = i + 1; j > left && vec[j] < vec[j - 1]; --j){ std::swap(vec[j], vec[j - 1]); } } } }}}}}} 파생형으로 이진 삽입 정렬(Binary insertionSort)이 있다. [[이진 탐색]]을 활용해 새로운 원소가 위치할 곳을 미리 찾아서 정렬하는 방식이다. 원소크기를 비교하는 조건 부분을 [math(\log{n})] 수준으로 낮춰 조금은 더 빠르게 수행할 수 있다는 점 정도.저장 버튼을 클릭하면 당신이 기여한 내용을 CC-BY-NC-SA 2.0 KR으로 배포하고,기여한 문서에 대한 하이퍼링크나 URL을 이용하여 저작자 표시를 하는 것으로 충분하다는 데 동의하는 것입니다.이 동의는 철회할 수 없습니다.캡챠저장미리보기